package com.yww.datastructure.queue;

import java.util.Iterator;

/**
 * @author yww
 * @description 环形数组实现队列(引入size来判满)
 * @since 2024/2/4 14:55
 */
public class ArrayQueue2<E> implements Queue<E> {
    private final E[] array;
    private int head;
    private int tail;
    private final int capacity;
    private int size = 0;

    public ArrayQueue2(int capacity) {
        // capacity就不用预留位置
        this.capacity = capacity;
        array = (E[]) new Object[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail] = value;
        // tail 后移
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E val = array[head];
        // head 后移
        head = (head + 1) % capacity;
        size--;
        return val;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        E val = array[head];
        return val;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            int step = 0;

            @Override
            public boolean hasNext() {
                // 对于没有预留一个位置，判断head下一个是否是tail得特殊处理
                // 队列如果是满，并且tail 和 head 是一样的，但是是第一次循环，tail和head就相差size个步数，这种情况必须返回true
                if (isFull() && tail == head && step == 0) {
                    return true;
                }
                return (p + step) % capacity != tail;
            }

            @Override
            public E next() {
                E val = array[(p + step) % capacity];
                step++;
                return val;
            }
        };
    }
}
